87. Робот

Бесконечная в обе стороны полоса ширины 1 разбита на клетки размера 1 × 1. В одной из них находится робот, который может двигаться из одной клетки в другую (на рисунке робот обозначен квадратиком). Его перемещения определяются программой, каждая команда в которой – это одна из трех больших латинских букв: L, R, S. Выполняя команду L, робот перемещается на одну клетку влево, команду R – на одну клетку вправо, а S – остается в той же самой клетке. Выполнение программы означает последовательное выполнение всех команд, записанных в ней.

Напишите программу, которая определит сколько различных клеток посетит робот.

Вход. Программа для робота – строка из символов L, R, S. Программа состоит не более чем из 10000 команд.

Выход. Выведите количество различных клеток, которые посетит робот, выполняя свою программу.

Пример входа	Пример выхода
RRSRRLRR	6

РЕШЕНИЕ

строки

Анализ алгоритма

Пусть робот изначально находится в клетке с номером 0. Будем моделировать его перемещения, запоминая номер самой левой l и самой правой r клетки куда он смог добраться. Тогда количество различных клеток, которые посетит робот, выполняя свою программу, составит r – l + 1.

Реализация алгоритма

Входную строку – программу для робота – храним в массиве s.

char s[10001];

Читаем входную строку.

gets(s);

Изначально считаем, что робот находится в точке с абсциссой x = 0. То есть на старте он побывал только на клетках интервала [l; r] = [0; 0].

l = x = r = 0;

Запускаем процесс моделирования программы робота. При движении вправо увеличиваем значение x на 1, при движении влево уменьшаем x на 1.

for(i = 0; i < strlen(s); i++)

{

if (s[i] == 'R') x++;

if (s[i] == 'L') x--;

После изменения значения x пересчитываем l и r.

if (x > r) r = x;

if (x < l) l = x;

}

Выводим количество различных клеток, которые посетит робот.

printf("%d\n",r - l + 1);

Реализация алгоритма – string

Читаем входную строку.

cin >> s;

Изначально считаем, что робот находится в точке с абсциссой x = 0. То есть на старте он побывал только на клетках интервала [l; r] = [0; 0].

l = x = r = 0;

Запускаем процесс моделирования программы робота. При движении вправо увеличиваем значение x на 1, при движении влево уменьшаем x на 1.

for (i = 0; i < s.size(); i++)

{

if (s[i] == 'R') x++;

if (s[i] == 'L') x--;

После изменения значения x пересчитываем l и r.

if (x > r) r = x;

if (x < l) l = x;

}

Выводим количество различных клеток, которые посетит робот.

cout << r - l + 1 << endl;

Реализация – динамический массив

#include <stdio.h>

#include <string.h>

int l, r, x, i;

char *s;

int main(void)

{

l = x = r = 0;

s = new char[10001];

gets(s);

for(i = 0; i < strlen(s); i++)

{

if (s[i] == 'R') x++;

if (s[i] == 'L') x--;

if (x > r) r = x;

if (x < l) l = x;

}

printf("%d\n",r - l + 1);

delete[] s;

return 0;

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

String s = con.nextLine();

int l, x, r;

l = x = r = 0;

for(int i = 0; i < s.length(); i++)

{

if (s.charAt(i) == 'R') x++;

if (s.charAt(i) == 'L') x--;

if (x > r) r = x;

if (x < l) l = x;

}

System.out.println(r-l+1);

con.close();

}

}

Python реализация

Читаем входную строку.

s = input()

Изначально считаем, что робот находится в точке с абсциссой x = 0. То есть на старте он побывал только на клетках интервала [l; r] = [0; 0].

r = l = x = 0

Запускаем процесс моделирования программы робота. При движении вправо увеличиваем значение x на 1, при движении влево уменьшаем x на 1.

for ch in s:

if ch == 'L': x += 1

if ch == 'R': x -= 1

После изменения значения x пересчитываем l и r.

r = max(r, x)

l = min(l, x)

Выводим количество различных клеток, которые посетит робот.

print(r - l + 1)